# 请判断一个链表是否为回文链表。
#
#  示例 1:
#
#  输入: 1->2
# 输出: false
#
#  示例 2:
#
#  输入: 1->2->2->1
# 输出: true
#
#
#  进阶：
# 你能否用 O(n) 时间复杂度和 O(1) 空间复杂度解决此题？
#  Related Topics 链表 双指针
#  👍 621 👎 0


# leetcode submit region begin(Prohibit modification and deletion)
# Definition for singly-linked list.
class ListNode:
    def __init__(self, x):
        self.val = x
        self.next = None


class Solution:
    def isPalindrome(self, head: ListNode) -> bool:

        """
        由于需要在 O(N) 时间复杂度和 O(1) 空间复杂度下完成
        这里可以考虑之前的链表翻转和 快慢指针
        快慢指针可以帮助定位到中间位置
        链表翻转前半部分，最后 慢指针继续往后，和前半段已经翻转过后的链表依次比较即可
        比较巧妙，结合了不少知识点
        :param head:
        :return:
        """
        if not head:
            return True
        slow = head
        fast = head
        prev = None
        nxt = slow.next
        while fast.next and fast.next.next:
            fast = fast.next.next
            slow.next = prev
            prev = slow
            slow = nxt
            nxt = nxt.next

        # 在 修改前记录 一下
        hasNext = not fast.next
        slow.next = prev
        # 如果是奇数个节点，那么 fast 最后走到结尾节点 ，slow 走到中间节点
        # 偶数节点，fast 会停留在倒数第二个节点
        # 另外需要考虑刚好只有两个节点偶数的情况，此时 fast slow 都指向头节点
        # 由于slow 修改了 next 值，导致此处通过if  not fast.next 判断出现问题
        # 所以先要通过 hasNext 记录一下
        if hasNext:

            slow = prev

        fast = nxt

        while slow:
            if slow.val != fast.val:
                return False

            else:
                slow = slow.next
                fast = fast.next

        return True


# leetcode submit region end(Prohibit modification and deletion)

head = ListNode(1)
head.next = ListNode(1)
# head.next.next = ListNode(1)
# head.next.next.next = ListNode(3)

print(Solution().isPalindrome(head))
